#!python3
# -*- coding: utf-8 -*-
# @Time    : 2024/6/7 17:10
# @Author  : 3tefanie
import random
from base64 import *

import gmpy2
from Crypto.Util.number import *


def b64urldecode(data):
    return b64decode(data).replace(b'-', b'+').replace(b'_', b'/')

def divide_pq(e, d, n):
    k = e * d - 1
    while True:
        g = random.randint(2, n - 1)
        t = k
        while True:
            if t % 2 != 0:
                break
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gmpy2.gcd(x - 1, n) > 1:
                p = gmpy2.gcd(x - 1, n)
                return (p, n // p)

gift = 84124447177743767918980903570270627615608281236226715968309581096421369832204039807371461411892208515839395002216485132893993980968089763647347358834567247594050449721455793217848033344349648370939409226981018544559395457908374763181184267300471140504112099876320748546180188849087217714232371203470663416667
Mod = 139867367320943171669967991208822345420590829754697976382072072962734823017467983007627838754695995701773941965204989831989734697257059961860040513404199380930944669935144902431760640501134127979625292042969004240269469336985008510166853698422773257590506334430744850890171018299011194360023742608665082066377
Ca = b'eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9.c2tmbmM.Mzc5ZGQxODM2YjA5Y2RkODFiOTVlOWU0ZmY4ZGQ2ZGM1MDNjNTEwMWRhZTYzNzg2NjI4OTgyZTU3MTZkZTBjMGE2MTE2YTQyMmFjMTY2N2U1MWY4Yzk0NjhhNTFhYWE0OWYwZTI4OTliZjFjYjkwZDg3YmYxN2MxZjY0MDFjZGM'
Cb = b'eyJhbGciOiJSUzI1NiIsInR5cCI6IkpXVCJ9.Y3Z1cW4.NmQ1Zjc3ZTEwMmM5ZGIwYTI2MWY4MGJhN2VlYWY3Y2Q4ZDExMDc2OTdlZTgwZTNhNzFhZTZkNzljZGZkMGFmMzYxNGZkMmEyMjlhZGZhN2M1NTgzYzc4OTNjMTVhMDBhMDY2YTdiMzk3MmViMTNmMDMyYTkyOGJlOGE1MDk0NWQ'
C = 26392799977002429281318957410345603007309891408627055595189077764390539316972320677722627751422579241052466419100658476552752139605724995701145328691914702530293164816623240066835637614638446501368316209584337883
e = 65537
c1 = int(b64urldecode(Ca.split(b".")[2]+b"="),16)
c2 = int(b64urldecode(Cb.split(b".")[2]+b"="),16)
a = bytes_to_long(b64urldecode(Ca.split(b".")[1]+b"="))
b = bytes_to_long(b64urldecode(Cb.split(b".")[1]+b"="))
#kn = gmpy2.gcd(pow(c1,e)-a,pow(c2,e)-b)
kn = 23599168453398158664430757151954398167247697087070567587728438808151745943911488939431427343547022828207780189704584429696317276579258497715308818367583809

for i in range(1,4):
    n = kn//i
    if n.bit_length()==512:
        print(i)
        #e*n*d = gift % Mod
        d = (gift * gmpy2.invert(e, Mod)*gmpy2.invert(n, Mod)) % Mod
        p, q = divide_pq(e, d, n)
        m = gmpy2.invert(p, Mod) * C % Mod
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)
            break